public class LRU {

    private static class Node {
        Node pre;
        Node next;
        int cache; // 模拟为cache

        public Node() {}

        public Node(int cache) {
            this.pre = null;
            this.next = null;
            this.cache = cache;
        }
    }

    private int capacity;
    private int len;
    private Node head;

    public LRU(int capacity) {
        this.capacity = capacity;
        this.len = 0;
    }

    public void access(int cache) {
        Node node = find(cache);
        if (node != null) {
            moveToHead(node);
        } else {
            node = new Node(cache);
            if (this.len >= this.capacity) {
                removeLastNode();
            }
            addNode(node);
        }
    }

    public Node find(int cache) {
        // 耗时为o(n)，可以使用hashmap存储降低查找耗时
        Node node = this.head;
        for (int i = 0; i < this.len; i ++) {
            if (node.cache == cache) {
                return node;
            }
            node = node.next;
        }
        return null;
    }

    public void addNode(Node node) {
        if (this.len == 0) {
            node.pre = node;
            node.next = node;
            this.head = node;
        } else {
            this.head.pre.next = node;
            node.pre = this.head.pre;
            node.next = this.head;
            this.head.pre = node;
            this.head = node;
        }
        this.len ++;
    }

    public void removeLastNode() {
        Node last = this.head.pre; // 获取最后一个节点
        this.head.pre = last.pre;
        last.pre.next = this.head;

        this.len --;
    }

    public void moveToHead(Node node) {
        if (node == this.head) {
            return;
        } else if (node.cache == this.head.pre.cache) {
            this.head = this.head.pre;
        } else {
            Node pre = node.pre;
            pre.next = node.next;
            node.next.pre = pre;

            this.head.pre.next = node;
            node.pre = this.head.pre;
            node.next = this.head;
            this.head.pre = node;
            this.head = node;
        }
    }

    public void show() {
        Node node = this.head;
        for (int i = 0; i < this.len; i++) {
            System.out.printf("-%d-", node.cache);
            node = node.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        System.out.println("LRU started...");
        LRU lru_cache = new LRU(10);
        int[] access_list = {4, 3, 1, 5, 7, 1, 4, 2, 5, 6, 2, 9, 8, 7, 0, 1, 0, 8, 11, 12, 2};
        for (int i = 0; i < access_list.length; i ++) {
            lru_cache.access(access_list[i]);
            lru_cache.show();
        }
        lru_cache.show();
    }
}
